package com.atguigu.sort;

import java.util.Random;

/**
 * @author 龍
 * 选择排序：先从所有的数据中查找到最小的数据，将这个数据和第一个数据进行交换，往复执行,执行n-1次。
 * 选择排序的时间复杂度为：n^2
 * 花费的时间大概为3秒。
 */
public class ChooseSort {
    public static void main(String[] args) {
        int[] array = new int[80000];
        for (int i = 0; i < array.length; i++) {
            array[i] = new Random().nextInt(8000000);
        }
        //System.out.println(Arrays.toString(array));
        System.out.println("排序前的时间：" + System.currentTimeMillis());
        //chooseSort(array);
        selectSort(array);
        System.out.println("排序后的时间：" + System.currentTimeMillis());
        //System.out.println(Arrays.toString(array));
    }

    /**
     * 选择排序的方法，传入参数为待排序的数组。这是我选择的算法，但是存在很多的问题，执行效率太低。
     * 问题：在寻找后续数组最小值的时候对其的值进行了修改。
     * @param arr
     */
    public static void chooseSort(int[] arr) {
        int temp = 0;
        int count = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            //假定当前坐标的数据为最小值
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) {
                    //发现有的值比当前的值小，则进行交换位置。
                    temp = min;
                    min = arr[j];
                    arr[j] = temp;
                    count++;
                }
            }
            //找到了后续数组的最小值。
            arr[i] = min;
        }
        System.out.println("count:" + count);
    }

    /**
     * 这个是老师的做法看起来比较的清晰明了，注重问题所在，在查找最小值的时候不修改值，只保存最小值。
     *
     * @param arr :等待排序的数组
     */
    public static void selectSort(int[] arr) {
        for (int j = 0; j < arr.length - 1; j++) {
            int minIndex = j;
            int min = arr[j];
            for (int i = j + 1; i < arr.length; i++) {
                if (min > arr[i]) {
                    min = arr[i];
                    minIndex = i;
                }
            }
            //两者的值进行交换
            arr[minIndex] = arr[j];
            arr[j] = min;
        }
    }
}
